package com.mzy.linear_struct.hot100.堆;

import com.mzy.linear_struct.utils.Utils;

import java.util.Arrays;
import java.util.LinkedList;

import static com.mzy.linear_struct.utils.Utils.swap;

/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午11:52
 * @Description:
 */
public class Pro347数组中的第K个最大元素 {

    public int topKFrequent(int[] nums, int k) {
        // 1. 对数组进行原地建堆
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            heapifyDown(nums, i, nums.length);
        }

        // 2. 获取前 k 个最大的元素
        int ans = nums[0];

        for (int i = nums.length - 1; i >= 0 && --k > 0; i--) {
            ans = nums[0];
            swap(nums, 0, i);
            heapifyDown(nums, 0, i);
        }
        return ans;
    }


    private void heapifyDown(int[] arr, int index, int length) {
        while (index * 2 + 1 < length) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int large = left;

            if (right < length && arr[large] < arr[right]) {
                large = right;
            }

            if (arr[large] <= arr[index]) {
                break;
            }

            swap(arr, index, large);
            index = large;
        }


    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println(new Pro347数组中的第K个最大元素().topKFrequent(new int[]{3, 2, 1, 5, 6, 4}, 6));
    }
}





























